Aiming at the problem of the poor real-time performance of Inertial Navigation System (INS)/Global Positioning System (GPS) integrated navigation system caused by GPS information delay, a processing method which takes advantage of dealing with various asynchronous measurements at an information fusion time in factor graph algorithm was proposed. Before the system received GPS information, the factor nodes of the INS information were added to the factor graph model, and the integrated navigation results were obtained by incremental inference to ensure the real-time performance of the system. After the system received the GPS information, the factor nodes about the GPS information were added to the factor graph model to correct the INS error, thereby ensuring high-precision operation of the system for a long time. The simulation results show that, the navigation state that has just been updated by GPS information can correct the INS error effectively, when the correction effect of real-time navigation state on INS error becomes worse, as the time of GPS information delay becomes longer. The factor graph algorithm avoids the adverse effects of GPS information delay on the real-time performance of INS/GPS integrated navigation system, and ensures the accuracy of the system.